﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
// 原题连接：https://leetcode.cn/problems/majority-element-ii/description/
/*
题目描述：
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。



示例 1：

输入：nums = [3,2,3]
输出：[3]
示例 2：

输入：nums = [1]
输出：[1]
示例 3：

输入：nums = [1,2]
输出：[1,2]


提示：

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109


进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
*/

// 开始解题：
// 方法——摩尔斯投票法
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int a = 0, cnt_a = 0; // 候选人a和它的血量
        int b = 0, cnt_b = 0; // 候选人b和他的血量
        for (auto x : nums) {
            if (cnt_a && a == x) {
                cnt_a++;
            }
            else if (cnt_b && b == x) {
                cnt_b++;
            }
            else if (cnt_a == 0) {
                a = x;
                cnt_a = 1;
            }
            else if (cnt_b == 0) {
                b = x;
                cnt_b = 1;
            }
            else {
                cnt_a--;
                cnt_b--;
            }
        }
        // 再次统计次数
        cnt_a = cnt_b = 0;
        for (auto x : nums) {
            if (x == a) {
                cnt_a++;
            }
            else if (x == b) {
                cnt_b++;
            }
        }
        vector<int> ret;
        if (cnt_a > nums.size() / 3) {
            ret.push_back(a);
        }
        if (cnt_b > nums.size() / 3) {
            ret.push_back(b);
        }
        return ret;
    }
};